package algorithm.array;

/**
 * leetcode : https://leetcode.com/problems/find-the-duplicate-number/description/
 * Difficulty : Medium
 *
 * 给一个数组，有n+1个数，其中数字的范围是[1,n] 这个条件很重要
 * 找到其中重复出现的数字。
 * 其中只有一个数字是重复出现的，并且可能出现大于2次
 *
 * 要求：
 * 不能改变数组元素，空间复杂度O(1)，时间复杂度不得大于O(N^2)
 *
 * 参考：
 * https://blog.csdn.net/monkeyduck/article/details/50439840
 * http://bookshadow.com/weblog/2015/09/28/leetcode-find-duplicate-number/
 *
 * 思路：
 * 抽屉原理
 *
 * @Author Antony
 * @Since 2018/7/24 19:55
 */
public class FindTheDuplicateNumber {

    public static void main(String[] args) {
        int[] arr = new int[]{1,2,4,5,6,6,3};
        System.out.println(findDuplicate(arr));
    }


    /**
     * beats 100.0% - 0ms
     * 思路和LinkedListCircleII 类似，快慢指针解法
     */
    public static int findDuplicate(int[] nums) {
        int slow = 0;
        int fast = 0;
        while(true){
            slow = nums[slow];
            fast = nums[nums[fast]];
            if(slow == fast) break;
        }

        int finder = 0;
        while(true){
            slow = nums[slow];
            finder = nums[finder];
            if(slow == finder) return slow;
        }
    }


    /**
     * beats 2.79% - 113ms
     * 时间复杂度：O(N^2)
     * 思路：两个指针
     */
    public static int findDuplicate_twoPointer(int[] nums) {
        for(int i=0; i<nums.length; i++){
            for(int j=i+1; j<nums.length; j++){
                if(nums[i] == nums[j]) return nums[i];
            }
        }
        return 0;
    }
}
